//
// Created by EDZ on 2022/2/7.
//

#ifndef INC_2022_1_DYNAMIC_H
#define INC_2022_1_DYNAMIC_H
#include "../head/common.h"
using namespace std;
/**
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。
 * @param grid
 * @return
 */
int minPathSum(vector<vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    int a[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i==0&&j==0){
                a[i][j] = grid[0][0];
            }
            if(i==0&&j!=0){
                a[i][j] = a[i][j-1]+grid[i][j];
            }
            if(j==0&&i!=0){
                a[i][j] = a[i-1][j]+grid[i][j];
            }
            if(i!=0&&j!=0){
                a[i][j] = min(a[i-1][j],a[i][j-1])+grid[i][j];
            }
        }
    }
    return a[n-1][m-1];
}

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * @param n
 * @return
 */
int climbStairs(int n) {
    if(n==1)
        return 1;
    int a[n];
    a[0] = 1;
    a[1] = 2;
    for(int i=2;i<n;i++){
        a[i] = a[i-1]+a[i-2];
    }
    return a[n-1];
}

/**
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @param word1
 * @param word2
 * @return
 */
int minDistance(string word1, string word2) {
    int n = word1.size();
    int m = word2.size();
    //表示将word1(0-i)转化为word2(0-j)需要的步数
    int arr[n+1][m+1];
    for(int i = 0;i<=n;i++){
        for(int j = 0;j<=m;j++){
            if(i==0||j==0){
                arr[i][j] = i+j;
            }else {
                arr[i][j] = min(min(arr[i - 1][j] + 1, arr[i][j - 1] + 1),
                                arr[i - 1][j - 1] + (word1[i - 1] != word2[j - 1]));
            }
        }
    }
    return arr[n][m];

}

vector<int> getNext(string s){
    vector<int> next(s.size());
    next[0] = -1;
    int j = -1,i = 0;
    while(i<s.size()-1){
        if(j==-1||s[i]==s[j]){
            i++;
            j++;
            next[i] = j;
        }else{
            j = next[j];
        }
    }
    return next;
}

int KMP(string s1,string s2){
    vector<int> next = getNext(s2);
    int i = 0,j = 0;
    int len1 = s1.size();
    int len2 = s2.size();
    while(i<len1&&j<len2){
        if(j==-1||s1[i]==s2[j]){
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    if(j>=len2){
        return (i-len2+1);
    }
    return -1;
}


#endif //INC_2022_1_DYNAMIC_H
